This application incorporates by reference Taiwanese application Ser. No. 88115162, filed Sep. 3, 1999.
1. Field of the Invention
The invention relates in general to a signal-processing method and a device therefor which combine a coordinate transformation with quantization and more particularly to a signal-processing method and a device therefore for achieving adaptive calculation quantity, image quality and bit rate.
2. Description of the Related Art
In digital signal compression, in order to reduce redundant data in coding, the coordinate transformation is usually applied for compressing image data or video data. That is because these data have good energy compact effect after the coordinate transformation. A good energy compact effect represents that, most energy is compacted at lower frequency bands, and little energy exists at higher frequency bands. After quantization, only data at lower frequency bands have codes. Therefore, the data are compressed.
Discrete Cosine Transform (DCT) is a coordinate transformation from the time domain to the frequency domain. There are four basic types of DCT, which are DCT-I, DCT-II, DCT-III and DCT-IV. What follows is the expression of the four types.
DCT-I:       y    ⁡          (      k      )        =                    (                  2          N                )                    1        /        2              ⁢          e      ⁡              (        k        )              ⁢                  ∑                  n          =          0                N            ⁢              xe2x80x83            ⁢                        e          ⁡                      (            n            )                          ⁢                              x            ⁡                          (              n              )                                ·                      cos            ⁡                          (                                                nk                  ⁢                                      xe2x80x83                                    ⁢                  π                                N                            )                                          
where n, k=0,1, . . . , N.
DCT-II:       y    ⁡          (      k      )        =                    (                  2          N                )                    1        /        2              ⁢          e      ⁡              (        k        )              ⁢                  ∑                  n          =          0                          N          -          1                    ⁢              xe2x80x83            ⁢                        x          ⁡                      (            n            )                          ·                  cos          ⁡                      (                                                            (                                                            2                      ⁢                      n                                        +                    1                                    )                                ⁢                k                ⁢                                  xe2x80x83                                ⁢                π                                            2                ⁢                N                                      )                              
where n, k=0,1, . . . , Nxe2x88x921.
DCT-III:       y    ⁡          (      k      )        =                    (                  2          N                )                    1        /        2              ⁢                  ∑                  n          =          0                          N          -          1                    ⁢              xe2x80x83            ⁢                        e          ⁡                      (            n            )                          ⁢                              x            ⁡                          (              n              )                                ·                      cos            ⁡                          (                                                                    (                                                                  2                        ⁢                        k                                            +                      1                                        )                                    ⁢                  n                  ⁢                                      xe2x80x83                                    ⁢                  π                                                  2                  ⁢                  N                                            )                                          
where n, k=0,1, . . . , Nxe2x88x921.
DCT-IV:       y    ⁡          (      k      )        =                    (                  2          N                )                    1        /        2              ⁢                  ∑                  n          =          0                          N          -          1                    ⁢              xe2x80x83            ⁢                        x          ⁡                      (            n            )                          ·                  cos          ⁡                      (                                                            (                                                            2                      ⁢                      k                                        +                    1                                    )                                ⁢                                  (                                                            2                      ⁢                      n                                        +                    1                                    )                                ⁢                                  xe2x80x83                                ⁢                π                                            4                ⁢                N                                      )                              
wheren n, k=0,1, . . . , Nxe2x88x921.
In the above expressions, when n=0,             e      ⁡              (        n        )              =          1              2              ,
else e(n)=1, and y(k) is an output from DCT and x(n) is an input to DCT. In practice, DCT-II is the most popular.
In the following statements, one-dimensional (1-D) DCT is first introduced for explaining two-dimensional (2-D) DCT.
Since the energy compact effect of DCT resembles to that of the Karhunen-Loe""ve transform, there are many researches about how to reduce computational complexity for 1-D DCT, for example, Lee""s DCT algorithm. The Lee""s DCT algorithm only needs 12 multiplication operations and 29 addition operations for 8-point 1-D DCT. In convention, the low-bound computational complexity of multiplication for N-point 1-D DCT is expressed as: xcexc(DCTN)=2n+1xe2x88x92nxe2x88x922; wherein N=2n and xcexc represents low-bound multiplication operations.
Therefore, the computational complexity for 8-point 1-D DCT of Lee""s algorithm meets the requirement of the low-bound calculation quantity.
It is assumed that Y(k) is the result of x(n)""s DCT transformation, wherein k and n=0, 1, 2, . . . Nxe2x88x921. The Forward DCT (FDCT) of x(n) can therefore be expressed as:                               Y          ⁡                      (            k            )                          =                              2            N                    ⁢                      xe2x80x83                    ⁢                      e            ⁡                          (              k              )                                ⁢                                    ∑                              n                =                0                                            N                -                1                                      ⁢                          xe2x80x83                        ⁢                                          x                ⁡                                  (                  n                  )                                            ⁢                              xe2x80x83                            ⁢                              cos                ⁡                                  [                                                                                    (                                                                              2                            ⁢                            n                                                    +                          1                                                )                                            ⁢                      k                      ⁢                                              xe2x80x83                                            ⁢                      π                                                              2                      ⁢                      N                                                        ]                                                                                        (        1        )            
,wherein when k=0,             e      ⁡              (        k        )              =          1              2              ,
else e(k)=1.
This type of DCT is the so-called DCT-II type. The Inverse DCT (IDCT) of the DCT-II type is expressed as:                               x          ⁡                      (            n            )                          =                              ∑                          k              =              0                                      N              -              1                                ⁢                      xe2x80x83                    ⁢                                    e              ⁡                              (                k                )                                      ⁢                          Y              ⁡                              (                k                )                                      ⁢                          cos              ⁡                              [                                                                            (                                                                        2                          ⁢                          n                                                +                        1                                            )                                        ⁢                    k                    ⁢                                          xe2x80x83                                        ⁢                    π                                                        2                    ⁢                    N                                                  ]                                                                        (        2        )            
wherein when k=0,             e      ⁡              (        k        )              =          1              2              ,
else e(k)=1.
Eq. (2) is also expressed as:                               x          ⁡                      (            n            )                          =                              ∑                          k              =              0                                      N              -              1                                ⁢                      xe2x80x83                    ⁢                                                    Y                ^                            ⁡                              (                k                )                                      ⁢                          cos              ⁡                              [                                                                            (                                                                        2                          ⁢                          n                                                +                        1                                            )                                        ⁢                    k                    ⁢                                          xe2x80x83                                        ⁢                    π                                                        2                    ⁢                    N                                                  ]                                                                        (        3        )            
wherein Ŷ=e(k)Y(k)
Based on odd k and even k, the following expression is obtained:                                           g            ⁡                          (              n              )                                =                                    ∑                              k                =                0                                                              N                  /                  2                                -                1                                      ⁢                          xe2x80x83                        ⁢                                          G                ⁡                                  (                  k                  )                                            ⁢                              cos                ⁡                                  [                                                                                    (                                                                              2                            ⁢                            n                                                    +                          1                                                )                                            ⁢                      k                      ⁢                                              xe2x80x83                                            ⁢                      π                                        N                                    ]                                                                    ⁢                  
                ⁢                              h            ⁡                          (              n              )                                =                                    ∑                              k                =                0                                                              N                  /                  2                                -                1                                      ⁢                          xe2x80x83                        ⁢                                          H                ⁡                                  (                  k                  )                                            ⁢                              cos                ⁡                                  [                                                                                    (                                                                              2                            ⁢                            n                                                    +                          1                                                )                                            ⁢                      k                      ⁢                                              xe2x80x83                                            ⁢                      π                                        N                                    ]                                                                                        (        4        )            
wherein
G(k)=Ŷ(2k), H(k)=Ŷ(2k+1)+Ŷ(2kxe2x88x921), k=0, . . . , N/2xe2x88x921, Ŷ(xe2x88x921)=0
From the above description, x(n) can be expressed as:                                           x            ⁡                          (              n              )                                =                                    g              ⁡                              (                n                )                                      +                                          (                                                      1                    /                    2                                    ⁢                                      xe2x80x83                                    ⁢                                      cos                    ⁡                                          [                                                                                                    (                                                                                          2                                ⁢                                n                                                            +                              1                                                        )                                                    ⁢                          π                                                N                                            ]                                                                      )                            ·                              h                ⁡                                  (                  n                  )                                                                    ⁢                  
                ⁢                              x            ⁡                          (                              N                -                n                -                1                            )                                =                                    g              ⁡                              (                n                )                                      -                                          (                                                      1                    /                    2                                    ⁢                                      xe2x80x83                                    ⁢                                      cos                    ⁡                                          [                                                                                                    (                                                                                          2                                ⁢                                n                                                            +                              1                                                        )                                                    ⁢                                                      xe2x80x83                                                    ⁢                          π                                                N                                            ]                                                                      )                            ·                              h                ⁡                                  (                  n                  )                                                                    ⁢                  
                ⁢                              n            =            0                    ,          …          ⁢                      xe2x80x83                    ,                                    n              /              2                        -            1                                              (        5        )            
It should be noticed that equations (2)xcx9c(5) come from IDCT. Because DCT is an orthogonal transform, the structure of FDCT is inversed from that of IDCT. The structure for 8-point 1-D DCT is shown in FIG. 1. In FIG. 1, X(0)xcx9cX(7) represent the input data, and y(0)xcx9cy(7) represent the output data. Herein, y(0)xcx9cy(7) are also called 1-D DCT outputs.
In image compression, it is usually to perform DCT on an image block with 8*8 pixels, and this kind of DCT transformation is usually a 2-D DCT transformation.
Here, another conventional 4*4 recursive 2-D DCT structure is taken as an example. Because this structure is a recursive one, its application can be extended to N*N 2-D DCT (N=2n). 8*8 2-D DCT structure can also be deduced, which is as shown in FIG. 2. In FIG. 2, x00, x01, . . . represent the input data, and y(m, n) (m, n=0xcx9c7) represent the 2-D DCT outputs. To realize this 2-D DCT structure, eight 1-D DCT structures are required. These 1-D DCT structures are the Lee""s 1-D DCT structure. The outputs from 1-D DCT are represented by ai (i=0xcx9c63). For simplicity, only some of the ai values are shown in FIG. 2. However, the non-shown a, values can be easily deduced from the figure. The scanning orders (or zig-zag order) represent the frequency-scanning orders of 2-D DCT outputs of the image block with 8*8 pixels. The output at a lower frequency band has also a lower scanning order. The 2-D DCT operation of an image block with 8*8 pixels totally includes 96 multiplication operations, 466 addition operations and 49 shift operations.
Generally speaking, when an image block with 8*8 pixels is performed by a 2-D DCT and quantization operation, the high frequency coefficients are often 0. In coding, these coefficients having a value of 0 are not taken into calculation.
In real practice, in order to obtain desirable quality of the reconstructed image, more calculations are required. However, more calculations cause the reduction of throughput rate or the increase of hardware cost. Therefore, it is important to trade off the computational complexity against the reconstructed image quality.
In image data compression, coordinate transformation and quantization operations are usually combined.
FIG. 3a is a block diagram of a conventional method for coordinate transformation and quantization. Herein, the coordinate transformation usually directs to DCT, which is a coordinate transformation from time domain (time coordinate) to frequency domain (frequency coordinate). In this conventional method, all 2-D DCT coefficients of the image block are calculated and then quantized for obtaining quantized outputs. The 2-D DCT unit 310 calculates all 2-D DCT coefficients, whose structure is shown as FIG. 2. The quantization unit 320 quantizes these 2-D DCT coefficients. The method to perform quantization is well known; so the detail is not described here.
The above-mentioned conventional method can have the optimized quality of the reconstructed image. However, the conventional method needs a great number of operations.
The block diagram of another conventional method, referred as the second one is shown in FIG. 3b. The second conventional method, or so-called xe2x80x9cfixed-point DCT methodxe2x80x9d, includes a fixed-point 2-D DCT unit 330 and a quantization unit 340. As mentioned above, a quantized DCT coefficient at high frequency is usually 0. According to this characteristic, this conventional method only calculates a fixed amount of DCT coefficients. For example, to an image block with 8*8 pixels, only the first 32 DCT coefficients in the zig-zag scan order are selected due to the energy compact effect. The structure of the fixed-point 2-D DCT unit 330 is obtained by simplifying the structure in FIG. 2, for calculating only first 32 coefficients in the zig-zag scan order.
However, the second conventional method in FIG. 3b can not get enough reconstructed image quality on a complex image block. The high frequency coefficients of the complex image block should not be ignored. Because the high-frequency coefficients are ignored by the second conventional method, the reconstructed image quality is not good enough. That is to say, the second conventional method does not have adaptability between computational complexity and reconstructed image quality.
FIG. 3c shows another conventional method, referred as the third one, for reducing computational complexity of DCT, which is called a xe2x80x9crecursive simplifying methodxe2x80x9d. This conventional method can be applied in H.263 video compression standard. In this system, the relation between a quantization factor Q and the DCT coefficients is predicted for calculating whole 8*8 DCT coefficients or to calculate only 4*4 DCT coefficients.
In H.263 video compression standard, the quantization factor Q ranges from 1 to 31. In an image including several image blocks, different image blocks may have different quantization factor Q. The third conventional method calculates a relation between an end of block (EOB) and the quantization factor Q in advance. The relation between EOB and the quantization factor Q is shown in FIG. 4. The definition of EOB is stated as follows. Signals having higher scanning orders than the EOB become zero after quantization. Herein, EOB is also called quantization end point.
Taking a curve of 99% in FIG. 4 for example. If Q is 9, it indicates that 99% of EOB is smaller than 30. So, the relation between EOB and Q is obtained. When Q is larger, EOB moves ahead and vice versa. An image block with a larger Q value has a lower demand on reconstructed image quality.
Through the relationship between Q and EOB, a proper Q threshold value is obtained. The 8th or 9th position in the zig-zag scan is the middle value in zig-zag orders (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 18, 19, 25) of an image block with 4*4 pixels. So, the zig-zag scan order 9 is the EOB for determining the Q threshold value. If the image block has a Q value larger than the Q threshold value, it is considered that the image block does not need high reconstructed image quality. In a low reconstructed image quality, the third conventional method calculates 8*8 DCT by using the 4*4 DCT unit 350 instead of the 8*8 DCT unit 360.
However, the 4*4 DCT unit 350 just performs approximate calculation but not real calculation. If an image block needs higher compression quality, the third conventional method utilities the 8*8 DCT unit 360 to calculate all 2-D DCT coefficients. The 2-D DCT coefficients, from 4*4 DCT 350 or 8*8 DCT 360, are quantized by the quantization unit 370 to obtain quantized outputs.
While the third conventional method is applied, if small EOB is used to obtain the large Q threshold value, higher computational complexity is required to get a higher reconstructed image quality. On the other hand, if large EOB is used to obtain a small Q threshold value, less computational complexity are required but a low reconstructed image quality is obtained.
It is therefore an object of the invention to provide an improved and simplified signal-processing device for having adaptability on reconstructed image quality and computational complexity and method therefor. The invention predicts a proper EOB and determines a simplified DCT structure by the EOB. The invention can archive lower computational complexity and less image quality distortion.
The invention achieves the above-identified objects by providing a new signal-processing method, for performing a DCT operation and a quantization operation on an input data to obtain quantized outputs. The input data includes an image block, and the image block corresponds to N (N is a natural number) DCT outputs and a search strategy. The N DCT outputs correspond to N scanning orders and N quantization parameters. The N scanning orders range from 0xcx9cNxe2x88x921. The search strategy includes some scanning orders. The signal-processing method includes the following steps of: determining one of the scanning orders as an End of Block (EOB) of the image block based on the search strategy; calculating DCT outputs corresponding to the scanning orders lower than the EOB; and performing a quantization operation on the calculated DCT outputs for obtaining the quantized outputs.
Besides, the invention further discloses a signal-processing method for performing a coordinate transformation operation and a quantization operation on an input data to obtain quantization outputs. The input data corresponds to N (N is a natural number) coordinate transformation outputs and a search strategy, The N coordinate transformation outputs correspond to N scanning orders and N quantization parameters, and the N scanning orders range from 0xcx9cNxe2x88x921. The search strategy includes part of the N scanning orders. In the signal-processing method, first of all, one of the scanning orders is considered as End of Block (EOB) of the input data based on the search strategy. Then the coordinate transformation outputs, corresponding to the scanning orders lower than the EOB, is calculated. Then, the quantization operation on the calculated coordinate transformation outputs is performed for obtaining the quantized outputs.
The input data are image block signals, multi-media signals, medical signals and the like. The coordinate transformation is a Discrete Cosine Transformation (DCT). The search strategy is an asymmetric binary search, a sequential search, a skip search and the like.
The procedure of determining EOB is stated as follows. (a) An initial value of an EOB parameter is selected as Nxe2x88x921. (b) A currently-used scanning order for a test operation is chosen based on the search strategy. (c) If the result of the test operation in step (b) is true, the currently-used scanning order is set as the EOB parameter; and if the currently-used scanning order is not an end condition of the search strategy, another scanning order is chosen as the currently-used scanning order based on the search strategy. (d) If the result of the test operation in step (b) is false; and the currently-used scanning order is not end condition of the search strategy, another scanning order is chosen as the currently-used scanning order based on the search strategy. (e) Above steps (b), (c) and (d) are repeated until the end condition of the search strategy is met. (f) The EOB parameter is set as EOB.
The test operation is stated as follows. The prediction value of a coordinate transformation output corresponding to the currently-used scanning order is obtained.
The prediction value is compared with the quantization parameter from the quantization table corresponding to the coordinate transformation output. The quantization parameter from the quantization table further corresponds to a quantization noise. When the prediction value is smaller than the quantization noise, the result of the test operation is true, and vice versa.
The invention further discloses a signal-processing device, for performing a Discrete Cosine Transform (DCT) operation and a quantization operation on input data to obtain quantizated outputs. The input data correspond to N (N is a natural number) DCT outputs, and the N DCT outputs corresponds to N frequency-scanning orders. The N scanning orders ranges from 0xcx9cNxe2x88x921. The signal-processing device includes: a frequency-scanning unit, comprising part of the frequency-scanning orders and outputting one as the currently-used frequency-scanning order; a DCT unit, comprising plurality of one-dimensional (1-D) DCT outputs and N 2-D DCT outputs, the DCT unit outputting one of the 1-D DCT outputs responding to the currently-used frequency-scanning order; a quantization unit, comprising N quantization parameter, the quantization unit outputting the currently-used quantization parameter responding the first frequency-scanning order; and a frequency-domain adapting unit, obtaining a compare result based on the one 1-D DCT output and the currently-used quantization parameter; wherein the frequency-scanning unit selects one of the N frequency-scanning orders as an end-of-block (EOB) of the 2-D DCT outputs, the DCT unit calculates part of 2-D DCT outputs whose scanning orders are lower than the EOB, and the quantization unit quantizes the calculated 2-D DCT outputs to obtain the quantizated outputs.
The frequency-domain adapting unit further includes: a shift unit, receiving Q(m,n) and outputting Q(m,n)/16, wherein Q(m,n) is the currently-used quantization parameter; and a compare unit, comparing |xcex1max| with Q(m,n)/16 to output the comparison result; wherein |xcex1max| is an absolute value of a maximum 1-D DCT output corresponding to the currently-used frequency-scanning order, and when |xcex1max| is smaller than Q(m,n)/16, the comparison result is true, and vice versa.
The invention further discloses a signal-processing device, for performing a coordinate transformation operation and a quantization operation on input data to obtain quantizated outputs. The input data correspond to N (N is a natural number) coordinate transformation outputs, and the N coordinate transformation outputs correspond to N scanning orders. The N scanning orders range from 0xcx9cNxe2x88x921. The signal-processing device includes: a scanning unit, comprising part of the scanning orders and outputting one scanning order as the currently-used scanning order; a coordinate transformation unit, comprising N coordinate transformation outputs and N prediction values, the coordinate transformation unit outputting a prediction value responding to the currently-used scanning order; a quantization unit, comprising N quantization parameters, and outputting the currently-used quantization parameter responding the currently-used scanning order; and a adapting unit, obtaining a comparison result based on the prediction value and the currently-used quantization parameter. The scanning unit selects one of the N scanning orders as an end-of-block (EOB) of the coordinate transformation outputs based on the compare result, the coordinate transformation unit calculates the coordinate transformation outputs whose scanning orders are lower than the EOB, and the quantization unit quantized the calculated coordinate transformation outputs to obtain the quantization output.
The adapting unit further includes: a shift unit, receiving the currently-used quantization parameter and outputting the currently-used quantization noise; and a compare unit, comparing the prediction value with the currently-used quantization noise to output the comparison result; when the prediction value is smaller than the currently-used quantization noise, the comparison result is true, and vice versa.